Tagless final

この辺は同義

tagless final

型クラスを用いてDSLを作る

ASTのような中間表現を介さない

tagless finalでDSLを定義する

DSLといえば、言語の定義とインタプリタが必要になるが、それらを型クラスを用いて表現する

型クラス

型に対する一連の操作

DSLの定義と言える

instance

特定の型ごとのDSLのインタプリタ

嬉しさ

通常のASTを定義するものと異なり中間表現を介さない

中間表現を介さないが、型クラスを使うことで、柔軟性を落とさずに表現できる

参考

Tagless Finalの概要と、類例との比較

具体的な小さいコードでの説明

ASTを使って定義することとの差異

記事の最後のコードをIDEに貼り付けて、ちょっと時間をかけて読むことで雰囲気を掴める

時間かけて読む価値ありそう

関連リンクもめっちゃある

hs

以下全てscala

itnialとfinalの違いを述べているが、Scalaなのでよくわからん

taglessとtagless finalって別物7日？

用語の意味

initial encoding

圏論用語に由来

通常の代数的データ型で定義したASTのこと？

主にAST内の「関数」をどう型安全に表現するかが論点っぽい

tagged initial encoding

通常の代数的データ型で定義したAST

この2つの値コンストラクタのことをtagと呼んでいる

実行時にこのtagを見て条件分岐して実行するのでtaggedと呼ばれる

tagless initial encoding

つまり、タグがない

だからtagless

final encoding

圏論由来の言葉ではない

圏論的には、ここでのinitialもfinalも両方initialなのらしい

initialと区別してのfinalという命名らしい

もっと良い命名あっただろう

domainごとに型クラスを作っっておく

どれもMonadを継承させることで、同じdo式の中で組み合わせて使える

code:hs

requestData userName = do

cache <- getFromCache userName

result <- case cache of

Just dataResult -> return dataResult

Nothing -> getFromSource userName

storeCache result

return result

これがDSLで記述されたコード

どのようなmonadに対してもこのコードを使える

実際にどういう操作をしてほしいかはinstanceを定義すればいい

これは、インタプリタを定義していることに等しい

2次元の拡張性

水平

同じ型クラスに対して、別のinstanceを作る

垂直

新しく別の型クラスを作る

色々な概念を包含したものらしい

部分評価

partial evaluation

ホスト言語の型システムで型付けされる

高階抽象構文

parserを作らなくていい

それってtagless final固有の嬉しさなんか？

何が嬉しい？

tagってなに？

対象言語の抽象構文木が型クラスで表現されており、 GADTやバリアント型を使っていない

特に「型付きの」DSLをGADT抜きで実装できている点が面白い

GADTにより、対象言語の型情報をうまくHaskellの型システムと結びつけて扱うことができ、型安全なインタプリタないしコンパイラを作ることができる

が、taglessな方法では中間表現を経由しないためにそもそもGADTが必要ない。

普通

抽象構文木を使う

GADTを使うこともある

GADTは型付きの抽象構文木を作るときに使ったりする

tagless

中間表現を使わない

型クラスを使う

GADTは不要

code:hs

class Lang (e :: * -> *) (array :: * -> *) | e -> array, array -> e where

binOp :: Op2 -> e D -> e D -> e D

unOp :: Op1 -> e D -> e D

iter :: e Int -> e Int -> e D -> (e Int -> e D -> e D) -> e D

int :: Integer -> e Int

double :: D -> e D

let_ :: String -> e a -> (e a -> e b) -> e b

at :: e Int -> e (array x) -> e x

通常のASTの一つ一つのパーツが型ではなく、関数で表現されている

通常ならこのASTの型Langに変換したあとに、それを処理するが、

a → Lang → b

taglesssの場合は、Langという中間表現が存在しないので、そこへの変換もそこからの変換もない

a → b

中間表現を介さずに直接変換することになる

関数の組み合わせが実際のASTみたいな感じになる

code:hs

tenTimes x =

iter (int 1) (int 10) (double 0.0) (\_ acc-> binOp Plus acc x)

ここがどれだけ書きやすいかは、Langのinstanceにする際の関数のinterfaceによる

ここまでできればもはやASTできてるようなものなので、そのまま直接実行できる

中間表現的な柔軟性の表現

元のでは、中間表現を介して、入力と出力の多様性を担保できた

taglessでは、型クラスを使うので、instanceを個別に作れば同様の多様性を担保できる